package com.future;


/**
 * Description:
 * n ������վ��һ�š�����һ���������� ratings ��ʾÿ�����ӵ����֡�
 * <p>
 * ����Ҫ��������Ҫ�󣬸���Щ���ӷַ��ǹ���
 * <p>
 * ÿ���������ٷ��䵽 1 ���ǹ���
 * ���������������ָ��ߵĺ��ӻ��ø�����ǹ���
 * �����ÿ�����ӷַ��ǹ������㲢������Ҫ׼���� �����ǹ���Ŀ ��
 * <p>
 * ?
 * <p>
 * ʾ��?1��
 * <p>
 * ���룺ratings = [1,0,2]
 * �����5
 * ���ͣ�����Էֱ����һ�����ڶ��������������ӷַ� 2��1��2 ���ǹ���
 * ʾ��?2��
 * <p>
 * ���룺ratings = [1,2,2]
 * �����4
 * ���ͣ�����Էֱ����һ�����ڶ��������������ӷַ� 1��2��1 ���ǹ���
 * ����������ֻ�õ� 1 ���ǹ��������������е�����������
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/candy
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 * <p>
 * eg1: ratings={5,6,9,2,1,0}
 * �ֵ��ǹ���{1,2,4,3,2,1}
 * ���ٷ��ص��ǹ���13
 * eg2: ratings={2,3,5,5,5,5}
 * �ֵ��ǹ���{1,2,3,1,1,1}
 * ���ٷ��ص��ǹ���9
 *
 * @Author: future
 * @Date:2022/3/23:23:57
 */
public class Solution_135 {


    /**
     * ˼·��
     * 1���ȴ������ұ��������������Ƚϣ������ǰ���ľ�+1������Ϊ1������ŵ�һ��left����
     * 2���ٴ���������������ڱȽϣ�����Ⱥ����ľ�+1������Ϊ1������ŵ�һ��right����
     * 3������left��right���飬��ͬһ���±��ֵ�õ����ֵ�ۼӾ��Ǵ�
     * eg:ratings={1,0,2}
     * left={1,1,2}
     * right={2,1,1}
     * ��Ӧ�±�����ֵ�ۼ�
     * ans = 2+1+2=5
     *
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }
        if (ratings.length == 1) {
            return 1;
        }
        int n = ratings.length;
        int[] left = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int[] right = new int[n];
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            } else {
                right[i] = 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.max(left[i], right[i]);
        }

        return ans;
    }
}
